|
In mathematics, a surjunctive group is a group such that every injective cellular automaton with the group elements as its cells is also surjective. Surjunctive groups were introduced by . It is unknown whether there can exist a group that is not surjunctive. ==Definition== A cellular automaton consists of a regular system of cells, each containing a symbol from a finite alphabet, together with a uniform rule called a ''transition function'' for updating all cells simultaneously based on the values of neighboring cells. Most commonly the cells are arranged in the form of a line or a higher-dimensional integer grid, but other arrangements of cells are also possible. What is required of the cells is that they form a structure in which every cell "looks the same as" every other cell: there is a symmetry of both the arrangement of cells and the rule set that takes any cell to any other cell. Mathematically, this can be formalized by the notion of a group, a set of elements together with an associative and invertible binary operation. The elements of the group can be used as the cells of an automaton, with symmetries generated by the group operation. For instance, a one-dimensional line of cells can be described in this way as the additive group of the integers, and the higher-dimensional integer grids can be described as the free abelian groups. The collection of all possible states of a cellular automaton over a group can be described as the functions that map each group element to one of the symbols in the alphabet. As a finite set, the alphabet has a discrete topology, and the collection of states can be given the product topology (called a prodiscrete topology because it is the product of discrete topologies). To be the transition function of a cellular automaton, a function from states to states must be a continuous function for this topology, and must also be equivariant with the group action, meaning that shifting the cells prior to applying the transition function produces the same result as applying the function and then shifting the cells. For such functions, the Curtis–Hedlund–Lyndon theorem ensures that the value of the transition function at each group element depends on the previous state of only a finite set of neighboring elements. A state transition function is a surjective function when every state has a predecessor (there can be no Garden of Eden). It is an injective function when no two states have the same successor. A surjunctive group is a group with the property that, when its elements are used as the cells of cellular automata, every injective transition function of a cellular automaton is also surjective. Equivalently, summarizing the definitions above, a group is surjunctive if, for every finite set , every continuous equivariant injective function is also surjective.〔Ceccherini-Silberstein & Coornaert (2010) p.57〕 The implication from injectivity to surjectivity is a form of the Garden of Eden theorem, and the cellular automata defined from injective and surjective transition functions are reversible. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Surjunctive group」の詳細全文を読む スポンサード リンク
|